#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : bheap.py
@Time    : 2022/12/01 23:08:13
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 大顶堆
"""

__all__ = ["heappush", "heappop", "heapify", "heapreplace", "heappushpop"]


def heappush(heap, item):
    """压入一个值, 并保持堆有效"""
    heap.append(item)
    _perc_up(heap, len(heap) - 1)  # 大值上浮


def _perc_up(heap, pos):
    p = (pos - 1) >> 1  # 找到上一层节点
    while p >= 0:
        if heap[p] < heap[pos]:
            heap[p], heap[pos] = heap[pos], heap[p]
        pos = p
        p = (p - 1) >> 1


def heappop(heap):
    """弹出最大值，并保持堆有效"""
    lastval = heap.pop()  # 如果堆为空，抛出索引异常；如果直有一个元素，直接返回弹出对象
    if heap:
        ret = heap[0]  # 如果堆中多于1个元素，应返回顶元素
        heap[0] = lastval
        _perc_down(heap, 0)  # 小值下沉
        return ret

    return lastval


def _perc_down(heap, n: int):
    max_index = len(heap) - 1
    max_n = (max_index - 1) >> 1  # 寻找最后一个非子节点

    while n <= max_n:
        x = n  # 与左右子节点相比，记录最小值下标
        m = (n << 1) + 1  # 左子节点
        if heap[m] > heap[x]:
            x = m

        m += 1  # 右子节点
        if m <= max_index and heap[m] > heap[x]:
            x = m

        if x != n:  # 如果当前节点是否需要与子节点交换
            heap[n], heap[x] = heap[x], heap[n]
            n = x
        else:
            break


def heapify(heap):
    if len(heap) < 2:
        return

    max_n = (len(heap) - 2) >> 1  # 寻找最后一个非子节点
    for n in range(max_n, -1, -1):
        _perc_down(heap, n)


def heapreplace(heap, item):
    ret = heap[0]
    heap[0] = item
    _perc_down(heap, 0)
    return ret


def heappushpop(heap, item):
    if heap and heap[0] > item:
        item, heap[0] = heap[0], item
        _perc_down(heap, 0)
    return item
